package
{
	import flash.display.Sprite;
	import flash.filters.GlowFilter;
	import flash.geom.Point;
	import flash.geom.Rectangle;

	public class QuadNode
	{
		public var boundingBox:Rectangle;
		public var children:Vector.<QuadNode>;
		public var point:Point;
		public var weight:int;
		public var depth:int = 0;
		public var totalDepth:int = 0;
		public var compressed:Boolean = true;
		
		public function QuadNode(depth:int = 0, compressed:Boolean = false)
		{
			weight = 1;
			this.compressed = compressed;
			this.depth = depth;
		}
		
		public function isInteresting():Boolean{
			var i:int, il:int;
			var numPoints:int = 0;
			if(children == null){
				if(point == null){
					return false;
				}
				else {
					return true;
				}
			}
			else {
				for(i = 0, il = children.length; i < il; i++){
					var child:QuadNode = children[i];

					if(child.children != null){
						return true;
					}
					else
					if(child.point != null){
						numPoints++;
					}						
				}
				
				if(numPoints >= 2){
					return true;
				}
				else {
					return false;
				}
			}
			return false;
		}
		
		public function remove(pointToRemove:Point, pointToInsertWeight:int = 1):void{
			if(children == null){
				if(this.point == null){
					return;
				}
				else{
					if(this.point.equals(pointToRemove)){
						this.weight -= pointToInsertWeight;
						if(this.weight <= 0){
							this.point = null
						}
					}
				}
			}
			else {
				var i:int, il:int;
				for(i = 0, il = children.length; i < il; i++){
					var child:QuadNode = children[i];
					
					if(child.boundingBox.containsPoint(pointToRemove)){
						child.remove(pointToRemove,1);
					}
				}
			}
			
			// kill sub quad tree if necessary
			if(!isInteresting() && children != null){
				for(i = 0, il = children.length; i < il; i++){
					child = children[i];
					if(child.point != null){
						this.point = child.point;
						this.weight = child.weight;
					}
				}
				
				this.children = null;
			}					
		}
		
		public function insert(pointToInsert:Point, pointToInsertWeight:int = 1):void{
			var inserted:Boolean = false;
			if(children == null){
				if(this.point == null){
					this.point = pointToInsert;
				}
				else {
					var pointToMove:Point = this.point;

					if(pointToMove.equals(pointToInsert)){
						this.weight += pointToInsertWeight;
					}
					else{
						this.point = null;
						this.children = SkipQuadtree.createQuadChildren(boundingBox, this.depth + 1, this.compressed);
						insert(pointToInsert, pointToInsertWeight);
						insert(pointToMove, this.weight);
					}
				}
				
				inserted = true;
			}
			else{
				var i:int, il:int;

				for(i = 0, il = children.length; i < il; i++){
					var child:QuadNode = children[i];
					if(child.boundingBox.containsPoint(pointToInsert)){
						inserted = true;
						child.insert(pointToInsert,1);
					}
				}
			}
			
			
			if(this.compressed && this.children){
				
				for(i = 0, il = children.length; i < il; i++){
					child = children[i];
					if(child.children && child.numInterestingChildren() == 1){
						child.children = child.getInterestingChild().children; 
					}
				}									
				
				if(inserted == false){
					var subChildren:Vector.<QuadNode> = this.children;
					var subChildrenLocation:Point = subChildren[0].boundingBox.topLeft;
					this.children = SkipQuadtree.createQuadChildren(boundingBox, this.depth + 1,this.compressed);
					for(i = 0, il = this.children.length; i < il; i++){
						child = children[i];
						if(child.boundingBox.containsPoint(subChildrenLocation)){
							child.children = subChildren;
						}
						if(child.boundingBox.containsPoint(pointToInsert)){
							child.insert(pointToInsert,1);
						}
					}					
				}
			}			
		}
		
		public function getInterestingChild():QuadNode{
			var i:int, il:int;
			var num:int = 0;
			for(i = 0, il = children.length; i < il; i++){
				if(children[i].isInteresting()){
					return children[i];
				}
			}			
			
			return null;
		}		
		
		public function numInterestingChildren():int{
			var i:int, il:int;
			var num:int = 0;
			for(i = 0, il = children.length; i < il; i++){
				if(children[i].isInteresting()){
					num++;
				}
			}			
			
			return num;
		}
		
		public function getMaxDepth():int{
			if(children != null){
				var i:int, il:int;
				var child:QuadNode;
				var numInteresting:int = 0;
				var maxDepth:int = 0;
				for(i = 0, il = children.length; i < il; i++){
					child = children[i];
					maxDepth = Math.max(maxDepth, child.getMaxDepth() + 1);
				}		
			}
			else {
				maxDepth = this.depth;
			}
			
			return maxDepth;
		}
		
		public function createImage():Sprite{
			return SkipQuadtree.drawTree(this, SkipQuadtree.IMAGE_SIZE);
		}
		
		public function find(pointToFind:Point):Boolean{
			if(children == null){
				if(this.point == null){
					return false;
				}
				else {
					if(this.point.equals(pointToFind)){
						return true;
					}
				}
			}
			else {
				var i:int, il:int;
				for(i = 0, il = children.length; i < il; i++){
					var child:QuadNode = children[i];
					if(child.boundingBox.containsPoint(pointToFind)){
						if(child.find(pointToFind)){
							return true;
						}
					}
				}				
			}

			return false;
		}
	}
}